/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 86186
 * Date: 2023-07-14
 * Time: 11:01
 */
public class Sort {

    // 插入排序
    public static void insertSort(int[] array){
        // write code  here
        for(int i = 1; i < array.length; i++) {
            int tmp = array[i];
            int j = 0;
            for(j = i - 1; j >= 0; j--) {
                if(array[j] > tmp) {
                    array[j+1] = array[j];
                }else {
                    break;
                }
            }
            array[j+1] = tmp;
        }
    }


    // 希尔排序
    public static void shellSort(int[] array){
        // write code  here
        int gap = array.length;
        while(gap > 1) {
            gap /= 2;
            for(int i = 0; i < array.length - gap; i++) {
                int tmp = array[i + gap];
                int j = i;
                while(j >= 0) {
                    if(array[j] > tmp) {
                        array[j+gap] = array[j];
                        j -= gap;
                    }else {
                        break;
                    }
                }
                array[j + gap] = tmp;
            }
        }
    }

    // 选择排序
    public static void selectSort(int[] array){
        // write code  here
        for(int i = 0; i < array.length-1; i++) {
            int minIndex = i;
            for(int j = i + 1; j < array.length; j++) {
                if(array[j] < array[minIndex]) {
                    minIndex = j;
                }
            }
            swap1(array,i,minIndex);
        }
    }

    private static void swap1(int[] array,int a,int b) {
        int tmp = array[a];
        array[a] = array[b];
        array[b] = tmp;
    }


// 堆排序
    public static void heapSort(int[] array){
        // write code  here
        creatHeap(array);
        int index = array.length-1;
        while(index > 0) {
            swap1(array,0,index);
            index--;
            shiftDown(0,array,index);
        }
    }

    private static void creatHeap(int[] array) {
        for(int p = (array.length-1-1) / 2; p >= 0; p--) {
            shiftDown(p,array,array.length-1);
        }
    }

    private static void shiftDown(int parent, int[] array,int len) {
        int child = 2 * parent + 1;
        while(child <= len) {
            if(child + 1 <= len && array[child + 1] > array[child]) {
                child++;
            }
            if(array[parent] < array[child]) {
                swap1(array,parent,child);
                parent = child;
                child = 2 * parent + 1;
            }else {
                break;
            }
        }
    }

    // 冒泡排序
    public static void bubbleSort(int[] array){
        // write code  here
        for(int i = 0; i < array.length - 1; i++) {
            boolean flg = false;
            for(int j = 0; j < array.length-i-1; j++) {
                if(array[j+1] < array[j]) {
                    swap1(array,j+1,j);
                    flg = true;
                }
            }
            if(!flg) {
                break;
            }
        }
    }

// 快速
    public static void quickSort(int[] array){
        // write code  here
        quick1(array,0,array.length-1);
    }

    private static void quick1(int[] array,int left,int right) {
        if(left >= right) return;
        int pivot = getPivot1(array,left,right);
        quick1(array,left,pivot-1);
        quick1(array,pivot+1,right);
    }


    private static int getPivot1(int[] array,int left,int right) {
        int tmp = left;
        int key = array[left];
        while(left < right) {
             while(left < right && array[right] >= key) {
                 right--;
             }
             while(left < right && array[left] <= key) {
                 left++;
             }
             swap1(array,left,right);
        }
        swap1(array,left,tmp);
        return left;
    }

    public static int[] sortArray(int[] nums) {
        quick(nums,0,nums.length-1);
        return nums;
    }

    private static void quick(int[] nums, int left, int right) {
        if(left >= right) return;
        int pivot = getPivot(nums,left,right);
        quick(nums,left,pivot-1);
        quick(nums,pivot+1,right);
    }


    private static int getPivot(int[] nums, int left, int right) {
        int key = nums[left];
        int prev = left;
        int cur = left + 1;
        while(cur <= right) {
            if(nums[cur] < key && nums[++prev] != nums[cur]) {
                swap(nums,prev,cur);
            }
            cur++;
        }
        swap(nums,left,prev);
        return prev;
    }

    private static void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}
